package leetcode.hot100;

import datastruct.list.ListNode;

public class Solution234 {

    public boolean isPalindrome(ListNode head) {
        //先用快慢指针找到中间节点
        ListNode fast=head, slow=head;
        while (fast!=null&&fast.next!=null){
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        //此时slow在中间,如果fast不空，那么链表有奇数个节点
        ListNode stop = slow; //固定前半段末尾
        if(fast!=null) slow = slow.next;
        //对前半段进行头插倒序
        ListNode virHead = new ListNode();
        fast = head;
        while (fast!=stop){
            //记录未插入的下一个节点
            ListNode tmp = fast.next;
            //头插
            fast.next = virHead.next;
            virHead.next = fast;
            //fast指向下一个未查节点
            fast = tmp;
        }
        //检验
        fast = virHead.next;
        while (slow!=null){
            if(fast.val!=slow.val) return false;
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
}
